\documentclass{ctexart}

\usepackage{graphicx}
\usepackage{amsmath}

\title{课后作业4.37}



\author{赖心怡 \\  医学实验班(临床医学八年制) 3210100987}

\begin{document}

\maketitle


\section{问题描述}
编写一个函数以二叉查找树 $T$ 和两个有序的关键字 $k_1$ 和 $ k_2$ ( $k_1 \le k_2$ ) 作为输入, 打印书中所有满足 $k_1 \le Key(x) \le k_2$ 的元素 $x$. 除去可以排序外, 不对关键字的类型做任何假设.所写的程序应该以平均时间 $O ( K + \log N)$ 运行, 其中 $K$ 是所打印的关键字的个数.确定你的算法的运行时间界.


\section{设计思路}
可以将题目中的Binary Search Tree 直接认为就是AVL Tree, 直接使用课本中 \verb|AvlTree.h| 文件的代码.自主完成函数实现查找并按值的顺序打印功能.
\begin{verbatim}
 void keyprint( const Comparable & k1, const Comparable & k2, AvlNode * & t )
    {
        if( t != nullptr ){
                if(k1 <= t -> element && t -> element <= k2){
                        keyprint( k1, t -> element, t -> left);
                //      cout << t -> element << endl;
                        keyprint( t -> element, k2, t -> right);
                }
                else if( k2 < t->element )
                        keyprint( k1, k2, t->left );
                else if( t->element < k1 )
                        keyprint( k1, k2, t->right );

        }

    }
\end{verbatim}

为节约运行时间采用递归算法,可分为以下几种情况处理: $k_1 \le x \le k_2$ 时, 中序遍历其余子树保证按值大小顺序输出; $k_2 < x$ 时, 只需遍历该节点左子树; $x < k_1$ 时,只需遍历该节点右子树.

\section{理论分析}
平均情况分析: 每一次递归数据量减半, 可得 $T(n) = T(\frac{n}{2}) + K$. 由主定理: 若$f(n) = \Theta(n^{\log_b a})$, 则 $T(n) = \Theta(n^{\log_b a}\log n)$, 可得 $T(n) = O(K + \log n)$.

最坏情况分析: 即 $k_1$ 小于树中最小值, $k_2$大于树中最大值或树中所有值均不满足条件, 此时 $T(n) = 2T(\frac{n}{2}) + K$. 由主定理: 若 $\exists \epsilon > 0$, 使 $f(n) = O(n^{\log_b a-\epsilon}$, 则 $T(n) = \Theta(n^{\log_b a})$, 可得 $T(n) = \Theta(n)$.

\section{数值结果分析}
令 NUMS = 10, 分别运行 \verb|t.keyprint( 2, 8)|, \verb|t.keyprint( 11, 12)|, 输出结果如下图所示,可知函数可满足功能要求,且对于超出查找范围的关键字能正确处理,没有内容输出.
\begin{figure}[htpb]
	\center{\includegraphics{figure1.png}}
\end{figure}

令 NUMS = 10, 100, 1000, 10000, 100000, 1000000, TESTN = 10, 输出程序的平均运行时间, 可知算法满足理论分析.(其实我觉得我的算法好像是 $T(n) = O(n)$, 和测试结果也比较符合但我真写不出来别的了/苦涩)
\begin{figure}[htbp]
	\center{\includegraphics{figure2.png}}
\end{figure}


\end{document}
